9. 树 Trees

树（Trees） 是一种十分常见且重要的数据结构，其常用于表示层次结构。

树的准确定义有两种形式：

递归定义：树是一个具有 根结点 与一系列 分支 的数据结构，其中每个分支也是一棵树。没有分支的树被称作 树叶。

家族关系定义：树是一系列 结点（Node） 的集合，其中每个结点可以是其它结点的 父节点 或 子结点。

我们可以借助广义表的思想在 Python 中实现一棵树：

# 构造函数
def tree(value, children = []):
	# 检查传入的孩子是否是一棵树
	for child in children:
		assert isTree(child), "A tree's children must be trees."
	return [value] + list(children)

# 选择函数
def getNodeValue(tree):
	return tree[0]

def getNodeChildren(tree):
	return tree[1:]

# 检查函数
def isTree(tree):
	if type(tree) != list or len(tree) < 1:
		return False
	for child in getNodeChildren(tree):
		if not isTree(child):
			return False
	return True

def isLeaf(tree):
	return not getNodeChildren(tree)

不过显式地调用 tree() 函数来构建一棵树过于繁琐。由于树具有良好的递归特性，我们同样也可以是通过实现递归函数来建立一棵树：

def fibTree(N):
	if N <= 1:
		return tree(N)
	else:
		left, right = fibTree(N-1), fibTree(N-2)
		return tree(getNodeValue(left) + getNodeValue(right),[left,right])

同理，基于树结构的操作函数一般也是递归函数：

def countLeaves(tree):
	if isLeaf(tree):
		return 1
	else:
		return sum([countLeaves(x) for x in getNodeChildren(tree)])